#include <stdio.h>
//顶点的最大个数
#define Max_VERtEX_NUM 20
//表示顶点之间的关系的变量类型
#define VRType int
//存储弧或者边额外信息的指针变量类型
#define InfoType char
//图中顶点的数据类型
#define VertexType int
//枚举图的 4 种类型
typedef enum { DG, DN, UDG, UDN} GraphKind;
//矩阵元素
typedef struct
{
    /* data */
    //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    VRType adj;
    //弧或边额外含有的信息指针
    InfoType * info;
} ArcCell, AdjMatrix[Max_VERtEX_NUM][Max_VERtEX_NUM];

//图
typedef struct {
    //存储图中顶点数据
    VertexType verxs[Max_VERtEX_NUM];
    //二维数组，记录顶点之间的关系
    AdjMatrix arcs;
    //记录图的顶点数和弧（边）数
    int verxnum, arcnum;
    //记录图的种类
    GraphKind gkind;
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G, VertexType v) {
    int i =0;
    //遍历一维数组，找到变量v
    for(; i < G->verxnum; i++) {
        if(G->verxs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if( i > G->verxnum) {
        printf("not found vertex\n");
        return -1;
    }
    return i;
}

//构造有向图
void CreateDG(MGraph * DG) {
    //输入图含有的顶点数和弧的个数
    scanf("%d,%d", &(DG->verxnum), &(DG->arcnum));
    //依次输入顶点本身的数据
    for(int i = 0; i < DG->verxnum ; i++) {
        scanf("%d", &(DG->verxs[i]));
    }
    //初始化二维矩阵，全部归0，指针指向NULL
    for(int i = 0; i < DG->verxnum; i++) {
        for(int j = 0 ; j < DG->verxnum; j++) {
            DG->arcs[i][j].adj = 0;
            DG->arcs[i][j].info = NULL;
        }
    }
    //在二维数组中添加弧的数据
    for(int i = 0; i < DG->arcnum; i++) {
        int v1, v2;
        //输入弧头和弧尾
        scanf("%d,%d", &v1, &v2);
        //确定顶点位置
        int n = LocateVex(DG, v1);
        int m = LocateVex(DG, v2);
        if(m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        //将正确的弧的数据加入二维数组
        DG->arcs[n][m].adj = 1;
    }
}

//构造无向图
void CreateDN(MGraph * DN) {
    scanf("%d,%d",&(DN->verxnum),&(DN->arcnum));
    for(int i = 0; i < DN->verxnum; i++) {
        scanf("%d", &(DN->verxs[i]));
    }
    //初始化二维矩阵，全部归0，指针指向NULL
    for(int i = 0; i < DN->verxnum; i++) {
        for(int j = 0 ; j < DN->verxnum; j++) {
            DN->arcs[i][j].adj = 0;
            DN->arcs[i][j].info = NULL;
        }
    }
    for(int i = 0; i < DN->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d", &v1, &v2);
        int n = LocateVex(DN, v1);
        int m = LocateVex(DN, v2);
        if(m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        //无向图的二阶矩阵沿主对角线对称
        DN->arcs[n][m].adj = 1;
        DN->arcs[m][n].adj = 1;
    }
}

//构造有向网，和有向图不同的是二阶矩阵中存储的是权值
void CreateUDG1(MGraph * UDG) {
    //输入图含有的顶点数和弧的个数
    UDG->verxnum = 6;
    UDG->arcnum = 10;
    //依次输入顶点本身的数据
    for(int i = 0; i < UDG->verxnum ; i++) {
        UDG->verxs[i] = i;
    }
    //初始化二维矩阵，全部归0，指针指向NULL
    for(int i = 0; i < UDG->verxnum; i++) {
        for(int j = 0 ; j < UDG->verxnum; j++) {
            UDG->arcs[i][j].adj = 0;
            UDG->arcs[i][j].info = NULL;
        }
    }
    //在二维数组中添加弧的数据
    /*
    {
        0 5 0 7 0 0
        0 0 4 0 0 0
        8 0 0 0 0 9
        0 0 5 0 0 6
        0 0 0 5 0 0
        3 0 0 0 1 0
    }
    */

    UDG->arcs[0][1].adj = 5;
    UDG->arcs[0][3].adj = 7;
    UDG->arcs[1][2].adj = 4;
    UDG->arcs[2][0].adj = 8;
    UDG->arcs[2][5].adj = 9;
    UDG->arcs[3][2].adj = 5;
    UDG->arcs[3][5].adj = 6;
    UDG->arcs[4][3].adj = 5;
    UDG->arcs[5][0].adj = 3;
    UDG->arcs[5][4].adj = 1;
}

//构造有向网，和有向图不同的是二阶矩阵中存储的是权值。
void CreateUDG(MGraph * UDG) {
    scanf("%d,%d",&(UDG->verxnum),&(UDG->arcnum));
    for(int i = 0; i < UDG->verxnum; i++) {
        scanf("%d",&(UDG->verxs[i]));
    }
    for(int i = 0; i < UDG->verxnum; i++) {
        for(int j =0 ; j < UDG->verxnum; j++) {
            UDG->arcs[i][j].adj = 0;
            UDG->arcs[i][j].info = NULL;
        }
    }
    for(int i = 0; i < UDG->arcnum; i++) {
        int v1, v2, w;
        scanf("%d,%d,%d", &v1, &v2, &w);
        int n = LocateVex(UDG, v1);
        int m = LocateVex(UDG, v2);
        if(m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        UDG->arcs[n][m].adj = w;
    }
}

//构造无向网。和无向图唯一的区别就是二阶矩阵中存储的是权值
void CreateUDN(MGraph* UDN) {
    scanf("%d,%d",&(UDN->verxnum),&(UDN->arcnum));
    for(int i = 0; i < UDN->verxnum; i++) {
        scanf("%d", UDN->verxs[i]);
    }
    for(int i = 0; i < UDN->verxnum; i++) {
        for(int j =0 ; j < UDN->verxnum; j++) {
            UDN->arcs[i][j].adj = 0;
            UDN->arcs[i][j].info = NULL;
        }
    }
    for(int i = 0; i < UDN->arcnum; i++) {
        int v1, v2, w;
        scanf("%d,%d,%d", &v1, &v2, &w);
        int n = LocateVex(UDN, v1);
        int m = LocateVex(UDN, v2);
        if(m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        //矩阵对称
        UDN->arcs[n][m].adj = w;
        UDN->arcs[m][n].adj = w;
    }
}

void CreateGraph(MGraph * G) {
    //选择图的类型
    scanf("%d", &(G->gkind));
    //根据所选类型，调用不同的函数实现构造图的功能
    switch (G->gkind)
    {
        case DG:
            return CreateDG(G);
            break;

        case DN:
            return CreateDN(G);
            break;

        case UDG:
            return CreateUDG(G);
            break;

        case UDN:
            return CreateUDN(G);
            break;
    
        default:
            break;
    }
}

void PrintGraph(MGraph G) {
    for(int i = 0 ; i < G.verxnum; i++) {
        for(int j = 0; j < G.verxnum; j++) {
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}

int main(int argc, char * argv[]) {
    //建立一个图的变量
    MGraph G;
    //调用创建函数，传入地址参数
    //CreateUDG1(&G);
    //调用创建函数，传入地址参数
    CreateGraph(&G);
    //输出图的二阶矩阵
    PrintGraph(G);
    return 0;
}